import java.util.Scanner;

public class Main11 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.print("请输入底数a：");
        long a = in.nextLong();
        System.out.print("请输入指数e的值：");
        int e = in.nextInt();
        System.out.print("请输入模数m的值：");
        long m = in.nextLong();
        long ret = modExpFun(a, e, m);
        System.out.println("结果为：" + ret);
    }

    private static long modExpFun(long a, int e, long m) {
        if(a <= 0 || e <= 0 || m < 0) {
            return -1;
        }
        if (m == 0) {
            return -2;
        }
        String s = Integer.toBinaryString(e);
        int len = s.length();
        long t = 1;
        for(int i = 0; i < len; i++) {
            t = (t * t) % m;
            char ch = s.charAt(i);
            if(ch == '1') {
                t = (t * a) % m;
            }
        }
        return t;
    }
}
